/**
 * Find the maximum total from the top of the triangle to the bottom by
 * moving to adjacent numbers on the row below.
 */

#include <iostream>
#include <algorithm>
#include "euler.h"

BEGIN_PROBLEM(18, solve_problem_18)
	PROBLEM_TITLE("Maximum sum travelling down a triangle of numbers")
	PROBLEM_ANSWER("1074")
	PROBLEM_DIFFICULTY(1)
	PROBLEM_FUN_LEVEL(1)
	PROBLEM_TIME_COMPLEXITY("n^2")
	PROBLEM_SPACE_COMPLEXITY("n^2")
END_PROBLEM()

static const int numbers[15][15] = 
{
	{ 75 },
	{ 95,64 },
	{ 17,47,82 },
	{ 18,35,87,10 },
	{ 20,4,82,47,65 },
	{ 19,1,23,75,3,34 },
	{ 88,2,77,73,7,63,67 },
	{ 99,65,4,28,6,16,70,92 },
	{ 41,41,26,56,83,40,80,70,33 },
	{ 41,48,72,33,47,32,37,16,94,29 },
	{ 53,71,44,65,25,43,91,52,97,51,14 },
	{ 70,11,33,28,77,73,17,78,39,68,17,57 },
	{ 91,71,52,38,17,14,91,43,58,50,27,29,48 },
	{ 63,66,4,68,89,53,67,30,73,16,69,87,40,31 },
	{ 4,62,98,27,23,9,70,98,73,93,38,53,60,4,23 },
};

static void solve_problem_18()
{
	int best[15];
	for (int j = 0; j < 15; j++)
		best[j] = numbers[14][j];

	for (int i = 13; i >= 0; i--)
	{
		for (int j = 0; j <= i; j++)
			best[j] = numbers[i][j] + std::max(best[j], best[j+1]);
	}
	std::cout << best[0] << std::endl;
}
